import java.util.ArrayList;
import java.util.LinkedList;

public class UFind{
        
	int ens_sommet[];
	int ens_oppose[];//pour chaque case dont l'indice est une racine, on met l'indice de la racine de l'ensemble oppose.
	int oppose[];
	int incr=1;
	
	/**
	 * Constructeur
	 */
	public UFind(){}
	
	/**
	* Constructeur
	* @param x nombre de variables de l'equation
	*/
	public UFind(int x)
	{
		ens_sommet = new int[x];
		ens_oppose = new int[x];
                
		for(int i = 0 ; i < x ; i++)
		{
			ens_sommet[i]=-1;
			ens_oppose[i] = -1;
		}
	}
          

	/**
	* Cherche pour une element x sa racine
	* @param x Element dont on veut la racine
	* @return Retourne l'indice de la racine de l'element trouve
	*/
	public int find(int element){
		int racine=ens_sommet[element]; //la racine
		int actuel_pere; //le pere du noeud courant
	    
		if (racine < 0)
			return element;
		
		//On parcourt l'arbre pour trouver la racine on la stocke dans papa
		while(ens_sommet[racine] >= 0)
		{
			racine = ens_sommet[racine];
		}
		//On va mettre la racine comme pere de tous les elements de la composants connexe               
		while(ens_sommet[element]!=racine)
		{
			actuel_pere = ens_sommet[element];
			ens_sommet[element] = racine;
			element = actuel_pere;
		}
		return racine;
	}

	/**
	* Fait l'union de deux arbres
	* @param e1 un element d'un arbre
	* @param e2 un element d'un arbre
	* @return True l'union c'est bien passe, false sinon( si e1 et e2 sont dans le meme arbre )
	*/
	public boolean union(int e1, int e2){
		if(find(e1) == findOppose(e2))
		{
			System.err.print("ERREUR: Le systeme d'equations est faux.\ne"+e1+"  ne doit pas etre oppose a "+e2);
			System.exit(0);
		}
		//rt1 et rt2 sont les racines des arbres dont e1 et e2 sont des éléments
		int rt1 = find(e1);
		int rt2 = find(e2);
		
		if(rt1==rt2)//e1 et e2 ont la meme racine
			return false;
		
		
		//Si le poids de rt1 est supérieur à celui de rt2 (ce sont des négatifs)
		if (ens_sommet[rt1] < ens_sommet[rt2])
		{
			System.out.println("C'est faux");
			//rt1 devient le père de rt2
			ens_sommet[rt2]=rt1;
			int n=ens_oppose[e2];
			ens_oppose[e2]=ens_oppose[e1];
			int n1;
			if(findOppose(e2)<ens_sommet.length)
				 {n1=ens_oppose[findOppose(e2)];}
			else 
				{n1=-1;System.out.println("je fais isjdqkld");}
			for(int i=0;i<ens_oppose.length;i++)
			{
				if(ens_oppose[i]==n && n!=-1)
				{
					System.out.println("hhhhh");
					ens_oppose[i]=ens_oppose[e1];
				}
				if(n1!=-1 && ens_oppose[i]==n1)
				{
					System.out.println("ca ne doit pas rentrer");
					ens_oppose[i]=ens_oppose[findOppose(e1)];
				}
			}
		}
		//Si ils ont le même poids
		else if (ens_sommet[rt1] == ens_sommet[rt2])
		{
			if(ens_oppose[e1]!=-1 && ens_oppose[e2]!=-1)
			{
				int n=ens_oppose[e2];
				int n1;
				if(findOppose(e2)<ens_sommet.length)
					n1=ens_oppose[findOppose(e2)];
				else 
					n1=-1;
				ens_oppose[e2]=ens_oppose[e1];
				ens_sommet[rt2]=rt1; //rt1 devient le père de rt2
				ens_sommet[rt1]--;
				for(int i=0;i<ens_sommet.length;i++)
				{
					if(ens_oppose[i]==n && n!=-1) ens_oppose[i]=ens_oppose[e1];
					if(n1!=-1 && ens_oppose[i]==n1)ens_oppose[i]=ens_oppose[findOppose(e1)];
				}
			}
			else if(ens_oppose[e1]!=-1 && ens_oppose[e2]==-1)
			{
				ens_oppose[e2]=ens_oppose[e1];
				ens_sommet[rt2]=rt1; //rt1 devient le père de rt2
				ens_sommet[rt1]--; //On augmente le poids (toujours des négatifs)
			}
			else if(ens_oppose[e2]!=-1 && ens_oppose[e1]==-1)
			{
				ens_oppose[e1]=ens_oppose[e2];
				ens_sommet[rt1]=rt2; //rt1 devient le père de rt2
				ens_sommet[rt2]--; //On augmente le poids (toujours des négatifs)
			}
			else
			{
				ens_sommet[rt2]=rt1; //rt1 devient le père de rt2
				ens_sommet[rt1]--; //On augmente le poids (toujours des négatifs)
				int nb_element=ens_sommet.length+incr;
				ens_oppose[e2]=nb_element;
				ens_oppose[e1]=nb_element;
				incr++;
			}
		}
		else
		{
			//rt2 devient le père de rt1
			ens_sommet[rt1]=rt2;
			ens_oppose[e1]=ens_oppose[e2];
		}		

		return true;
	}
	
    /**
     * Trouve l'oppose d'un element e s'il en a un
     * @param e une variable de l'equation
     * @return Renvoie l'ensemble qui est oppose a l'ensemble possedant e, sinon -1
     */
    public int findOppose(int e){
    	int element=ens_oppose[find(e)];
        if (element > -1)// Si element a un oppose
            return element;// On renvoie son oppose
        else// Sinon on renvoie -1 car l'element n'as pas d'oppose 
            return -1;
    }
    
    /**
     * Fait l'union de deux ensembles oposes
     * @param e1 a variable of an equation
     * @param e2 a variable of an equation
     */
    public void unionOppose(int e1, int e2)
    {
    	
    	int racine_e1=find(e1);
    	int racine_e2=find(e2);
        // Si 2 variables appartiennent au meme ensemble
        // elles ne peuvent pas etre opposees donc le systeme d'equation est faux.
        if(racine_e1 == racine_e2)
        {
            System.err.print("ERREUR: Le systeme d'equations est faux.\ne"+e1+" doit etre different de "+e2);
            System.exit(0);
        }

        
        if(findOppose(e2) == -1)//Si jamais l'ensemble auquel e2 appartient n'a pas d'oppose
        {
        	System.out.println("je suis la");
            if(findOppose(e1) == -1)// Si l'ensemble de e1 non plus n'a pas d'oppose
            {
                //Alors on les mets opposes l'un a l'autre
                ens_oppose[racine_e1] = racine_e2;
                ens_oppose[racine_e2] = racine_e1;
                
            }
            else//Si e1 a deja un oppose
            {
            	System.out.println("je suis isiisis");
                // On dit a e2 d'appartenir a l'ensemble oppose a e1
            	if(findOppose(e1)>=ens_sommet.length)
            	{
            		int n=ens_oppose[e1];
            		for(int i=0;i<ens_sommet.length;i++)
            		{
            			if(ens_oppose[i]==n)
            				ens_oppose[i]=e2;
            		}
            	}
            	System.out.println("je fais l'union de "+findOppose(e1));
                if(union(e2,findOppose(e1))==false)
                {
                	System.out.println("Je regroupe deux groupes");
                	int n=ens_oppose[e2];
                	if(n>=ens_sommet.length)
                	{
                		for(int i=0;i<ens_oppose.length;i++)
                		{
                			if(ens_oppose[i]==n)
                				ens_oppose[i]=racine_e1;
                		}
                	}
                	else 
                		ens_oppose[e2]=racine_e1;
                }
                else
                {
                	System.out.println("je rentre");
                	ens_oppose[e2]=racine_e1;
                }
            }
        }
        else // Si e2 a un oppose
        {
        	System.out.println("je suis la");
        	if(findOppose(e2)>=ens_sommet.length)
        	{
        		int n=ens_oppose[e2];
        		System.out.println(n);
        		for(int i=0;i<ens_sommet.length;i++)
        		{
        			if(ens_oppose[i]==n)
        				ens_oppose[i]=e1;
        		}
        	}
        	// Alors dans ce cas-la e1 appartiendra a l'ensemble oppose a e2
        	
        	if(union(e1,findOppose(e2))==false)
        	{
        		System.out.println("Je regroupe deux groupes");
        		int n=ens_oppose[e1];
        		System.out.println("le nombre est "+n);
        		if(n>=ens_sommet.length)
        		{
        			System.out.println("le nombre que je change par "+racine_e2);
        			for(int i=0;i<ens_oppose.length;i++)
        			{
        				if(ens_oppose[i]==n)
        					ens_oppose[i]=racine_e2;
        			}
        		}
        		else
        			ens_oppose[e1]=racine_e2;
        	}
    		
        }
    }
    
    
    /**
     * Trouve le plus grand element du tableau ens_oppose
     * @return le plus grand element du tableau
     */
    int max()
    {
    	int res=ens_oppose[0];
    	for(int i=0;i<ens_oppose.length;i++)
    	{
    		if(res<ens_oppose[i])
    			res=ens_oppose[i];
    	}
    	return res;
    }
    
    /**
     * Creer un tableau pour pouvoir faciliter la separation des groupes et groupes opposes
     * Il suffira de regarder la case 	ayant l'indice du groupe oppose pour savoir dans quel groupe il est
     * affecte un numero positif a un groupe et son numero oppose negatif a son groupe oppose
     * le numero positif est pour le plus grand groupe
     * 
     */
    public ArrayList<Integer> oppose()
    {
    	int numero=0;
    	int max=max()+1;
    	ArrayList<Integer> multiensemble=new ArrayList<Integer>();
    	oppose=new int[max];
    	int[] maxi=new int[max];
    	
    	//initialise le tableau maxi et oppose a 0    	
    	for(int i=0;i<max;i++)
    	{
    		oppose[i]=0;
    		maxi[i]=0;
    	}
    	
    	//dasn maxi:pour chaque groupe compte le nombre d'element
    	//dans oppose:assemble les groupes avec leur oppose
    	for(int i=0;i<ens_oppose.length;i++)
    	{
    		if(oppose[ens_oppose[i]]==0)
    		{
    			oppose[ens_oppose[i]]=numero;
    			if(ens_oppose[i]<ens_sommet.length)
    				oppose[findOppose(ens_oppose[i])]=numero*-1;
    			numero++;
    			
    		}
    		maxi[ens_oppose[i]]++;
    	}
    	
    	System.out.println("Compte le card de chaque ensemble");
    	for(Integer inn:maxi)
    	{
    		System.out.print(inn+" ");
    	}
    	System.out.println();
    	
    	numero--;
    	for(int i=0;i<numero;i++)
    	{
    		multiensemble.add(0);
    	}
    	System.out.println("je suis lalalal");
    	//fais en sorte que le groupe de plud grand cardinal soit en positif et son oppose en negatif
    	for(int i=0;i<max;i++)
    	{
    		if(maxi[i]!=0)
    		{
    			if(i<ens_sommet.length)
    			{
	    			int opp=findOppose(i);
	    			if(opp!=-1 &&maxi[i]>maxi[opp] && oppose[i]<oppose[opp])
	    			{
	    				oppose[i]=oppose[i]*-1;
	    				oppose[opp]=oppose[opp]*-1;
	    				
	    			}
    			}
    		}
    	}
    	
    	System.out.println("Mes ensembles sont:");
    	for(Integer inn:oppose)
    	{
    		System.out.print(inn+" ");
    	}
    	System.out.println();
    	
    	
    	//creer un multiensemble contenant la soustraction du groupe avec son oppose
    	int temp;
    	for(int i=0;i<max;i++)
    	{
    		if(maxi[i]!=0 )
    		{
    			if(i<ens_sommet.length)
    			{
		    		if(maxi[i]>maxi[findOppose(i)])
		    		{
		    			System.out.println(i+" le cardinal de cette ensemble est "+maxi[i]);
		    			temp=oppose[i];
		    			if(temp<0)
		    			{
		    				temp=temp*-1;
		    			}
		    			System.out.println("j'ai ça: "+multiensemble.get(temp-1));
		    			int n=multiensemble.get(temp-1)+maxi[i];
		    			System.out.println("maintenant j'ai:"+n);
		    			multiensemble.set(temp-1,n);
		    		}
		    		else if(maxi[i]==maxi[findOppose(i)])
		    		{
		    			System.out.println(i+" le cardinal de cette ensemble est "+maxi[i]);
		    			temp=oppose[i];
		    			if(temp<0)
		    			{
		    				temp=temp*-1;
		    			}
		    			System.out.println("j'ai ça: "+multiensemble.get(temp-1));
		    			multiensemble.set(temp-1, multiensemble.get(temp-1)+maxi[i]);
		    			System.out.println("maintenant j'ai:"+multiensemble.get(temp-1));
		    			maxi[i]++;
		    		}
		    		else
		    		{
		    			System.out.println(i+" le cardinal de cette ensemble est "+maxi[i]);
		    			temp=oppose[i];
		    			if(temp<0)
		    		    {
		    		    	temp=temp*-1;
		    		    }
		    			System.out.println("j'ai ça: "+multiensemble.get(temp-1));
		    			multiensemble.set(temp-1, (multiensemble.get(temp-1))-maxi[i]);
		    			System.out.println("maintenant j'ai:"+multiensemble.get(temp-1));
		    		}
    			}
    			else
    			{
    				temp=oppose[i];
	    			System.out.println("j'ai ça: "+multiensemble.get(temp-1));
	    			multiensemble.set(temp-1, (multiensemble.get(temp-1))+maxi[i]);
	    			System.out.println("maintenant j'ai:"+multiensemble.get(temp-1));
    			}
    		}
    	}
    	
    	System.out.println("le multi ensemble");
    	for(Integer i:multiensemble)
    	{
    		System.out.print(i+" ");
    	}
    	System.out.println();
    	
    	for(int i=0;i<max;i++)
    		System.out.print(oppose[i]+" ");
    	System.out.println();
    	
    	return multiensemble;
    }
    
    /**
     * Pour un tableau boolean, on va affecter la valeur de chaque variable selon son ensemble
     * @param tableau qui est la solution pour chaque ensemble
     */
    public void une_solution(int[] tableau)
    {
    	int [] tab=new int[ens_sommet.length];
    	int groupe;
    	for(int i=0;i<ens_oppose.length;i++)
    	{
    		if(oppose[ens_oppose[i]]>0)
    		{
    			tab[i]=tableau[oppose[ens_oppose[i]]-1];
    		}
    		else
    		{
    			tab[i]=(tableau[-1*oppose[ens_oppose[i]]-1]+1)%2;
    		}
    		System.out.print(tab[i]+" ");
    	}
    	System.out.println();
    }
    
}
